package com.lx.algorithm.code;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-12-30 09:39:57
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-12-30     张李鑫                     1.0         1.0 Version
 */
public class Code03 {
    /**
     * 括号有效配对是指：
     * 1）任何一个左括号都能找到和其正确配对的右括号
     * 2）任何一个右括号都能找到和其正确配对的左括号
     * 返回一个括号字符串中，最长的括号有效子串的长度
     */
    public static int check(String str) {
        if (str == null || str.length() < 2) {
            return 0;
        }
        int n = str.length();
        int res = 0;
        char[] chars = str.toCharArray();
        int[] dp = new int[n];
        for (int i = 1; i < dp.length; i++) {
            //只有）这个括号的时候字符才可能有效
            if (chars[i] == ')') {
                //找到有效字符以后要找到上一个有效字符的索引的前一个位置看看是不是（
                //l代表上一个有效字符的前一个位置
                int l = i - dp[i - 1] - 1;
                //如果l==（ 还要找到（前一个dp的信息 把有效字符累加
                if (chars[l] == '(') {
                    dp[i] = dp[i - 1] + 2 + (l > 0 ? dp[l - 1] : 0);
                }
                res = Math.max(res, dp[i]);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        //          00240024
        String str = "(())(())(((())))()()()()";
        System.out.println(check(str));
    }
}
